package com.github.yangyishe.p100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 72. 编辑距离
 * https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 *
 * 你可以对一个单词进行如下三种操作：
 *
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 *
 *
 * 示例 1：
 *
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 * 示例 2：
 *
 * 输入：word1 = "intention", word2 = "execution"
 * 输出：5
 * 解释：
 * intention -> inention (删除 't')
 * inention -> enention (将 'i' 替换为 'e')
 * enention -> exention (将 'n' 替换为 'x')
 * exention -> exection (将 'n' 替换为 'c')
 * exection -> execution (插入 'u')
 *
 *
 * 提示：
 *
 * 0 <= word1.length, word2.length <= 500
 * word1 和 word2 由小写英文字母组成
 */
public class Problem72 {
    public static void main(String[] args) {
        String word1="intention";
        String word2="execution";

        Problem72 problem72 = new Problem72();
        int i = problem72.minDistance(word1, word2);
        System.out.println("i = " + i);

    }

    /**
     * 思路:
     * 子问题, 是word1的前i个字符, 到word2的前j个字符的最短路径. 即为dis(i,j)或者dis[i][j]
     * 其公式为:
     * if chars[i]==chars[j]: dis[i][j]=Math.min(dis[i-1][j]+dis[i][j-1]+dis[i-1][j-1])+1
     * else: dis[i][j]=Math.min(dis[i-1][j]+dis[i][j-1]+dis[i-1][j-1]-1)+1
     *
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        //1. 初始化dp数组
        int[][] dps=new int[word1.length()+1][word2.length()+1];

        //2. 初始化
        for(int i=0;i<=word1.length();i++){
            dps[i][0]=i;
        }
        for(int i=0;i<=word2.length();i++){
            dps[0][i]=i;
        }

        //3. 递归遍历
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                int minDis = Integer.min(dps[i - 1][j], dps[i][j - 1]);
                minDis=Integer.min(minDis,(word1.charAt(i-1)==word2.charAt(j-1)?-1:0)+dps[i-1][j-1]);
                dps[i][j]=minDis+1;
            }
        }

        return dps[word1.length()][word2.length()];
    }

    /**
     * 思路:
     * 极端情况下,
     * 最不理想的情况, 最小距离, 是Math.max(word1.length(),word2.length())
     * 最理想的情况, 最小距离, 是Math.abs(word1.length()-word2.length())
     * 另, 从word1到word2, 和从word2到word1的最小距离, 是一个逆过程, 一定是相等的.
     *
     * 假定, word1.len<=word2.len
     * 如实例2: word1=intention, word2=execution. word1.len=word.len=9
     * indexOf(char,offset)=index: char表示要搜索的字符; offset表示搜索的开始位置(不包含当前位置); index表示查找到的索引(表示左侧第一个索引), 如果找不到则返回-1
     * dis(start,end)=distance: start表示查询字符串的开始索引, end表示查询字符串的结束索引. 左闭右开. distance表示最小距离.
     * 逐次推进:
     * 1. word1.len==1
     * word1="i" ->
     * if indexOf(0,0)==-1: return dis(0,1)=n=9;
     * else: return dis(0,1)=n-1=8.
     *
     * actual->indexOf(0,0)==6, dis(0,1)=8
     * 并且当end-start=1时, 均可按照以上算法求出.
     *
     * 2. word1.len==2
     * word1="in"
     * if indexOf(0,-1)==-1:
     *      return dis(0,2)=dis(1,2)
     * else:
     *      if indexOf(1,-1)==-1: return dis(0,1)=n-1;
     *      else:
     *          index0=indexOf(0,-1)
     *          if indexOf(1,index0)==-1: return n-1
     *          else: return n-2;
     * actual->n-2
     *
     * 朴素的讲, 当word1的某个子字符串child1, 在word2中按照顺序排列的最大子数组size=m, 则最小距离就是n-m
     * 同时, child1需要维护一个集合, 所有可能的顺序索引集合.
     * word1.len==1时, 继续保留最左侧的一个索引即可, 记为index1. 本轮最多新增curSize(1)=~[0,1]
     * word1.len==2时, 首先记录所有第二单字符对应的索引单集合;
     *      最左侧的索引单集合一定保留index2_0;
     *      如果存在在索引1右侧的字符, 则同样保留第一个, 并将索引1复制出一份放在左侧indexs2_1_;
     *      其余的都不需要保留;
     *      (可能最左侧索引单集合和索引1右侧合并的索引, 恰好是一个集合).
     *      curSize(2)=~[0,2]; sumSize(2)=curSize(1)+curSize(2)=~[0,3]
     * word1.len==3时, 记录所有第三字符对应的索引集合;
     *      最左侧保留一个index3+0;
     *      其余情况, 如果有已存在集合的右侧情况的, 则均复制出一份, 并取对应的第一遍历到索引(可能取到的索引并不相同, 相同索引的情况, 取size最大即可).
     *      curSize(3)=~[0,sumSize(2)+1]=~[0,4];sumSize(3)=curSize(1)+curSize(2)+curSize(3)
     *
     * word1.len=m时, 记录所有第m字符对应的索引集合;
     *      针对每个字符, 查找左侧size最大的已存在集合, 不存在按照空集合算;
     *      从左到右开始, 维护一个size, 只要size比前面的大, 就记录拷贝一份新集合; 否则不拷贝.
     *      如果遇到重复的字符, 在相同的位置上如果构建的新集合比原来集合size大, 则用新集合, 否则用原来的集合.
     *
     * 最后找到size最大的集合, 则最小距离=n-maxSize.
     * 算法复杂度为O(n^2)
     *
     * 记录二维数组时, 第一维的size, 可直接设置为n.
     *
     * @param word1
     * @param word2
     * @return
     */
    /*public int minDistance(String word1, String word2) {
        // 获取目标字符数组word2中, word1每个char对应的索引集合(此处效率可优化, 但可读性起见先用这种方式)
        Map<Character, List<Integer>> char2TargetIndexMap=new HashMap<>();
        for(int i=0;i<word2.length();i++){
            char2TargetIndexMap.putIfAbsent(word2.charAt(i),new ArrayList<>());
            char2TargetIndexMap.get(word2.charAt(i)).add(i);
        }

        //1. 初始化二维数组
        int[][] childIndexsArr=new int[word2.length()][];


        // (不需要考虑初始化)
        //2. 遍历推进
        for(char c1:word1.toCharArray()){
            List<Integer> targetIndexList = char2TargetIndexMap.get(c1);
            if(targetIndexList==null){
                continue;
            }
            int lastTargetIndex=-1;
            for (Integer targetIndex : targetIndexList) {
                int[] beforeIndexs=new int[0];
                // 此处需要遍历size最大的beforeIndexs
                for(int i=targetIndex;i>lastTargetIndex;i--){
                    if(childIndexsArr[i]!=null){
                        if(childIndexsArr[i].length>beforeIndexs.length){
                            beforeIndexs=childIndexsArr[i];
                        }

                    }
                }
                int[] oldChildIndexs=childIndexsArr[targetIndex];
                if(oldChildIndexs==null||oldChildIndexs.length<beforeIndexs.length+1){
                    int[] newIndexs=new int[beforeIndexs.length+1];
                    System.arraycopy(beforeIndexs, 0, newIndexs, 0, beforeIndexs.length);
                    newIndexs[newIndexs.length-1]=targetIndex;
                    childIndexsArr[targetIndex]=newIndexs;
                }
                lastTargetIndex=targetIndex;

                // 此处还差一处只处理最左的char的逻辑, 但只影响效率
            }

        }

        //3. 返回->计算最大相似位的算法正确, 但最终问题的算法还是有问题.
        int maxChildSize=0;
        for(int[] childIndexs:childIndexsArr){
            if(childIndexs!=null){
                maxChildSize=Integer.max(maxChildSize,childIndexs.length);
            }
        }

        return Integer.max(word1.length(),word2.length())-maxChildSize;
    }*/
}
